package com.example.demo.linkedlist;

/**
 * @description 基于单链表实现 LRU（Least Recently Used 最少使用策略）
 * @auther lijiewei
 * @date 2021/8/16 11:16
 */
public class LRUBaseLinkedList<T> {

    /** 默认链表容量. */
    private final static Integer DEFAULT_CAPACITY = 10;
    /** 头结点. */
    private SNode<T> headNode;
    /** 链表长度. */
    private Integer length;
    /** 链表容量. */
    private Integer capacity;

    public LRUBaseLinkedList() {
        this.headNode = new SNode();
        this.capacity = DEFAULT_CAPACITY;
        this.length = 0;
    }

    public LRUBaseLinkedList(Integer capacity) {
        this.headNode = new SNode();
        this.capacity = capacity;
        this.length = 0;
    }

    /**
     * 添加数据
     * @param data 数据
     * @return
     * @author lijiewei
     * @date   2021/8/16 11:38
     */
    public void add(T data) {
        SNode preNode = findPreNode(data);
        if (preNode != null) {
            //删除对应节点，在链表头重新插入相应节点
            deleteElemOptim(preNode);
            intsertElemAtBegin(data);
        } else {
            //超过了容量，删除未尾结点
            if (length >= this.capacity) {
                deleteElemAtEnd();
            }
            intsertElemAtBegin(data);
        }
    }

    /**
     * 查询数据对应元素的前一个节点
     * @param data 数据
     * @return
     * @author lijiewei
     * @date   2021/8/16 11:38
     */
    private SNode findPreNode(T data) {
        SNode preNode = this.headNode;
        while (preNode.getNext() != null) {
            //比较后一个节点的值
            if (data.equals(preNode.getNext().getElement())) {
                return preNode;
            }
            preNode = preNode.getNext();
        }
        return null;
    }

    /**
     * 删除 preNode 节点的下一个节点
     * @param preNode 节点
     * @return
     * @author lijiewei
     * @date   2021/8/16 11:42
     */
    private void deleteElemOptim(SNode preNode) {
        preNode.setNext(preNode.getNext().getNext());
        length--;
    }

    /**
     * 链表头部加入 data 数据对应节点
     * @param data 数据
     * @return
     * @author lijiewei
     * @date   2021/8/16 11:44
     */
    private void intsertElemAtBegin(T data) {
        SNode nextNode = headNode.getNext();
        headNode.setNext(new SNode(data, nextNode));
        length++;
    }

    /**
     * 删除尾节点
     * @return
     * @author lijiewei
     * @date   2021/8/16 13:43
     */
    private void deleteElemAtEnd() {
        SNode preNode = headNode;
        //空链表直接返回
        if (null == preNode.getNext()) {
            return;
        }

        //倒数第二个节点
        while(null != preNode.getNext().getNext()) {
            preNode = preNode.getNext();
        }
        preNode.setNext(null);
        length--;
    }

    /**
     * 打印所有节点
     * @return
     * @author lijiewei
     * @date   2021/8/16 13:55
     */
    public void printAll() {
        SNode nextNode = headNode.getNext();
        while(null != nextNode) {
            System.out.print(nextNode.getElement() + ",");
            nextNode = nextNode.getNext();
        }
        System.out.println();
    }

}
